#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
class Solution
{
private:
    bool is_res(unordered_map<char, int> &s_count, unordered_map<char, int> &t_count)
    {
        for (auto &e : t_count)
        {
            if (s_count.find(e.first) == s_count.end() || s_count[e.first] < t_count[e.first])
                return false;
        }
        return true;
    }

public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> t_count;
        for (auto e : t)
            t_count[e]++;
        // 起始位置 长度
        pair<int, int> res{-1, -1};
        // 答案区间起始
        int start = -1;
        bool is_start = true;
        unordered_map<char, int> s_count;
        // 记录每一个位置
        queue<int> jump_queue;
        for (int i = 0; i < s.size(); i++)
        {
            // 当前字符属于t
            if (t_count.find(s[i]) != t_count.end())
            {
                // 每个符合条件字符出现的位置
                jump_queue.push(i);
                // 初始化区间
                if (start == -1)
                {
                    start = jump_queue.front();
                    jump_queue.pop();
                    is_start = false;
                }
                // 统计[start,i]区间的次数
                s_count[s[i]]++;
                // 如果得到了一个答案
                while (is_res(s_count, t_count))
                {
                    int new_len = i + 1 - start;
                    // 如果新串比旧串短或者目前还没有答案就更新
                    if (res.first < 0 || new_len < res.second)
                    {
                        res.first = i - new_len + 1;
                        res.second = new_len;
                    }
                    // 找下一个满足条件的字串
                    if (!--s_count[s[start]])
                    {
                        s_count.erase(s[start]);
                    }
                    // 更新区间
                    start = jump_queue.front();
                    jump_queue.pop();
                }
            }
        }
        if (res.first == -1)
            return "";
        return s.substr(res.first, res.second);
    }
};